package F.树;



import java.time.temporal.Temporal;
import java.util.*;

public class _107_二叉树的层次遍历II {
    /**
     * 借助栈 按照层次push进去
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        List<List<Integer>> lists =new LinkedList<>();
        if (root == null){
            return lists;
        }

        Stack<List<Integer>> stack = new Stack<>();
        Queue<TreeNode> container = new LinkedList<>();//层次遍历结点
        //List<Integer> numCon = new LinkedList<>();

        container.add(root);

        while (!container.isEmpty() ){
            List<Integer> numCon = new LinkedList<>();
            int size = container.size();
          //  stack.push(container);
            while (size>0){
                TreeNode node =container.poll();
                numCon.add(node.val);//报空指针异常？？---poll出来 size不会自动减 所以还要size--
                if (node.left != null){
                    container.add(node.left);
                }
                if (node.right != null){
                    container.add(node.right);
                }
                size--;
            }
            //一次while是一层 一层完了放入stack
            stack.push(numCon);
            numCon.clear();
        }

//        while (stack!=null){
//            lists.add(stack.pop());
//
//        }
        for (int i= stack.size()-1;i>=0;i--){
            lists.add(stack.get(i));
        }

        return lists;
    }


    //题解：思路同自解
    //但是直接用头插法--直接listsadd(0, level);就能实现
    public List<List<Integer>> levelOrderBottom1(TreeNode root) {

        List<List<Integer>> lists =new LinkedList<>();
        if (root == null){
            return lists;
        }


        Queue<TreeNode> container = new LinkedList<>();//层次遍历结点
        //List<Integer> numCon = new LinkedList<>();
        container.add(root);
        while (!container.isEmpty() ){
           // List<Integer> numCon = new LinkedList<>();
            List<Integer> numCon = new ArrayList<>();
            int size = container.size();
            while (size>0){
                TreeNode node =container.poll();
                numCon.add(node.val);//报空指针异常？？
                if (node.left != null){
                    container.add(node.left);
                }
                if (node.right != null){
                    container.add(node.right);
                }
                size--;
            }
            //一次while是一层 一层完了放入stack
            lists.add(0,numCon);
        }

        return lists;
    }

}
